/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package matrici;

import java.text.DecimalFormat;

/**
 *
 * @author simone
 */
public class ProgrammazioneLineare {

    public ProgrammazioneLineare() {
        double[][] A = {{1, 1}, {1, 0}, {0, 1}};
        double[] b = {20, 12, 16}, c = {18, 12.5};
        simplex(A, b, c);
    }

    double[] simplex(double[][] A, double[] b, double[] c) {
        System.out.println(stampaMatrice(A));
        int[] B, N;
        double v = 0;
        int l, e, variabili = A[0].length, vincoli = A.length;
        N = new int[variabili];
        for (int i = 0; i < variabili; i++) {
            N[i] = i;
        }
        B = new int[vincoli];
        for (int i = 0; i < vincoli; i++) {
            B[i] = i + variabili;
        }
        e = firstPositive(c);

//        System.out.println("pre");
//        System.out.println(stampaMatrice(A));
//        System.out.println(OperazioniSuMatrici.stampaMatrice(b));
//        System.out.println(OperazioniSuMatrici.stampaMatrice(c));
//        //for (int q = 0; q < 2; q++) {

        while (e != -1) {
            l = findL(A, b, e);
            if (l == -1) {
                return null;
            }
            double pivot = A[l][e];

            b[l] /= pivot;
            A[l][e] = 1;
            for (int i = 0; i < A[0].length; i++) {
                A[l][i] /= pivot;
            }

            for (int i = 0; i < A.length; i++) {
                double mul = A[i][e];
                if (i != l) {
                    for (int j = 0; j < A[0].length; j++) {

                        if (j != e) {
                            A[i][j] += mul * (-A[l][j]);
                        } else {
                            A[i][j] = mul * (-A[l][j]);
                        }
                    }
                    b[i] += mul * -b[l];
                }
            }
            double mul = c[e];
            for (int i = 0; i < c.length; i++) {
                if (i != e) {
                    c[i] += mul * (-A[l][i]);
                } else {
                    c[i] = mul * (-A[l][i]);
                }
            }
            v += mul * b[l];

            int temp = N[e];
            N[e] = B[l];
            B[l] = temp;

            //System.out.println(q);
//            System.out.println("A");
//            System.out.println(stampaMatrice(A));
//            System.out.println("b");
//            System.out.println(OperazioniSuMatrici.stampaMatrice(b));
//            System.out.println("B");
//            System.out.println(OperazioniSuMatrici.stampaMatrice(B));
//            System.out.println("c");
//            System.out.println(OperazioniSuMatrici.stampaMatrice(c));
//            System.out.println("N");
//            System.out.println(OperazioniSuMatrici.stampaMatrice(N));
//            System.out.println("v\n"+v);
//            System.out.println("");
            e = firstPositive(c);
        }

        double[] res = new double[variabili];
        for (int i = 0; i < vincoli; i++) {
            if (B[i] < variabili) {
                res[B[i]] = b[i];
            }
        }

        System.out.println(OperazioniSuMatrici.stampaMatrice(res));
        return res;
    }

    int findL(double[][] A, double[] b, int e) {
        double min = Double.MAX_VALUE;
        int l = -1;
        for (int i = 0; i < A.length; i++) {
            double temp = b[i] / A[i][e];
            if (temp > 0) {
                if (temp < min) {
                    min = temp;
                    l = i;
                }
            }
        }
        return l;
    }

    int firstPositive(double[] a) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] > 0) {
                return i;
            }
        }
        return -1;
    }

    public String stampaMatrice(double[][] matrice) {
        int n = matrice.length;
        int m = matrice[0].length;
        String res = "";
        DecimalFormat df = new DecimalFormat("#####0.####");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res += df.format(matrice[i][j]) + "\t";
            }
            res += "\n";
        }
        return res;
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        ProgrammazioneLineare programmazioneLineare = new ProgrammazioneLineare();
    }
}